/*************************************************************************
  > File Name: 3_bag_get.c
  > Author: IvanLxy
  > Mail: yoyiyyo@163.com 
  > Created Time: Fri 20 Mar 2020 05:25:46 PM CST
************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
//封装物品信息
typedef struct good_info
{
    double price;      //物品单位价值
    double sum_price;  //物品总价值
    double get_rate;   //装入此物品的重量占总重的比例
    int get_weight;    //装入此物品的物品重量
    int sum_weight;    //此物品总重量
}good_info;

void print_array(good_info *goods, int n);

/*********按物品效益，重量比值做序排列***************/
void insert_sort_by_price(good_info *goods, int n)
{
    int i, j;
    good_info tmp;

    for(i = 1; i < n; i++)
    {
        ////////CMP(i-1,i)//////////
        tmp = goods[i];
        j = i - 1;
        /////////CMP(j,tmp)//////////
        while ((j >= 0) && (tmp.price > goods[j].price))
        {
            goods[j + 1] = goods[j];
            j--;
        }
        goods[j + 1] = tmp;//while不执行时，(j,tmp)--goods[j+1]本就等于tmp
        //////////后比前大，互换位置，大的在前////////////////
    }
}

///先装单位价值高的，装不下一整个跳出，把该物品拆分直到装满
void bag(good_info *goods, int capacity, int n)
{
	int left;
    int i;

    //每个物品所使用的质量--置0
    for(i = 0; i < n; i++)
    {
    	goods[i].get_weight = 0;
    }

    left = capacity;                     //背包剩余容量
    
    //insert_sort_by_price之后goods已经按单位价值从高到低排列
    for(i = 0; i < n; i++)
    {
        if(left <= goods[i].sum_weight )   //当该物品重量大与剩余容量跳出
        {
            break;
       	}
        //当可以放下时，对物品的使用比例，和使用重量：做标记
        goods[i].get_weight = goods[i].sum_weight;
        goods[i].get_rate  = 1.0;

        left -= goods[i].sum_weight;                        //确定背包新的剩余容量
    }
    //物品重量装不下一整个break之后|或者整装结束需要切分而装时-把背包挤满
    if(i < n)
    {
    	goods[i].get_weight = left;                          //该物品所要放的量
    	goods[i].get_rate = left * 1.0 / goods[i].sum_weight;//该物品所要放的量
    }

 }

 void print_array(good_info *goods, int n)
 {
 	int i;

 	for(i = 0; i < n; i++)
	{
		printf("%d\t%lf\t%lf\t%d\t%lf\n",
				goods[i].sum_weight,
				goods[i].sum_price,  goods[i].price,
				goods[i].get_weight, goods[i].get_rate);
	}
    
}

//贪心法解决背包问题
int main(int argc, char const *argv[])
{
	int n = 10;
    int i;
    int  capacity;
    //n个物品的goods_info结构体空间申请
    good_info *goods;//定义一个指针
    goods = (good_info *)malloc(sizeof(good_info) * n);
	if (goods == NULL)
	{
		printf("malloc failed\n");
		exit(1);
	}

    memset(goods, 0, sizeof(good_info) * n); //Memset 用来对一段内存空间全部设置为某个字符，（这里是0）
    srand(time(NULL));//srand函数是随机数发生器的初始化函
   	for(i = 0; i < n; i++)
	{
		goods[i].sum_weight = rand() % 50 +1;
		goods[i].sum_price = rand() % 100 + 1;
		goods[i].price = goods[i].sum_price/goods[i].sum_weight;//得出物品的重量比
	}

	printf("背包的最大容量：");
    scanf("%d", &capacity);

    insert_sort_by_price(goods, n);//先排序
	bag(goods, capacity, n);//再装包
   	print_array(goods, n);//最后打印

	free(goods);//释放空间

	return 0;
}

